﻿#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>

using namespace std;

struct Data
{
    string key;
    int times;

    Data()
    {
        key = "";
        times = 0;
    }

    Data(string input)
    {
        key = input;
        times = 1;
    }
};

struct DataComparator
{
    bool operator()(const Data* a, const Data* b){
        return a->times < b->times;
    }
};

static void topK(const string* strArr, const size_t arrSize, vector<string>& vec, int K)
{
    unordered_map<string, Data*> dataMap;
    for (int i = 0; i < arrSize; ++i)
    {
        const string& curStr = strArr[i];
        Data* exist = dataMap[curStr];
        if (exist)
        {
            ++exist->times;
        }
        else
        {
            dataMap[strArr[i]] = new Data(curStr);
        }
    }

    priority_queue<Data*, vector<Data*>, DataComparator> heap;
    for (const auto& data_map : dataMap)
    {
        if (heap.size() < K) {
            heap.push(data_map.second);
        } else {
            const auto top = heap.top();
            if (data_map.second->times > top->times) {
                heap.pop();
                heap.push(data_map.second);
            }
        }
    }

    while (!heap.empty()) {
        const auto top = heap.top();
        vec.push_back(top->key);
        heap.pop();
    }

    for (const auto& data_map : dataMap)
    {
        delete(data_map.second);
    }
}

/**
 * 给定一个字符串类型的数组arr，求其中出现次数最多的前K个.
 *
 * 例如： ["apple","apple","boy","zoo","apple","echo","dog","echo"], 找到出现次数最多的前2个字符串。
 * "apple"出现三次，"echo"出现两次，故前2名是:"apple", "echo".
 *
 * 思路：
 * 使用HashMap记录每个字符串的出现次数，声明一个容量为K的小根堆，小根堆没有满的情况下，
 * 使用HashMap中的键值对塞入堆中；小根堆满了，则将要塞入的下一组键值对与堆顶的键值对的值对比，大于就弹出堆顶，
 * 并将该组键值对塞入堆顶，直到将所有的键值对都处理完。
 */
int main_MostTopK()
{
    vector<string> vec;
    string strArr[] = {"apple","apple","boy","zoo","apple","echo","dog","bird","zoo"};
    size_t arrSize = sizeof(strArr)/sizeof(strArr[0]);
    topK(strArr, arrSize, vec, 3);
    for (auto& str : vec) {
        printf("%s\n", str.c_str());
    }
    
    return 0;
}